class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        i = len(str(n)) - 1

        ans = self.count1(i)
        for j in range(1, 10):
            # print(n, ":", j, "->", (j + 1) * pow(10, i), (j * pow(10, i)))
            if n >= (j + 1) * pow(10, i):
                ans += self.count2(i, 1)
            else:  # n >= j * pow(10, i)
                ans += self.count3(i, n - (j * pow(10, i)), [j])
                break
        return ans

    def count1(self, i):
        """前面没有数的情况下10*i-1的有重复数量"""
        ans = self.count1(i - 1) + 9 * self.count2(i - 1, 1) if i > 1 else 0
        # print("COUNT1:", i, "->", ans)
        return ans

    def count2(self, i, t):
        """前面有t个不同的数的情况下10*i-1的有重复数量"""
        if i == 0:
            ans = 0
        elif i == 1:
            ans = t
        else:
            ans = 10 ** (i - 1) + 9 * self.count2(i - 1, t + 1)
        # print("COUNT2:", i, t, "->", ans)
        return ans

    def count3(self, i, n, lst):
        """计算前面有lst中的数的情况下，n的重复数量"""
        if i == 0:
            ans = 0
        elif i == 1:
            ans = len([j for j in range(n + 1) if j in lst])
        else:
            ans = 0
            for j in range(10):
                if n >= (j + 1) * pow(10, i - 1):
                    if j in lst:
                        ans += pow(10, i - 1)
                    else:
                        ans += self.count2(i - 1, len(lst) + 1)
                elif n >= j * pow(10, i - 1):
                    if j in lst:
                        ans += (n + 1) - j * pow(10, i - 1)
                    else:
                        ans += self.count3(i - 1, n - j * pow(10, i - 1), lst + [j])
                else:
                    break

        # print("COUNT3:", i, n, lst, "->", ans)

        return ans


if __name__ == "__main__":
    print(Solution().numDupDigitsAtMostN(20))  # 1
    print(Solution().numDupDigitsAtMostN(100))  # 10
    print(Solution().numDupDigitsAtMostN(121))  # 22
    print(Solution().numDupDigitsAtMostN(1000))  # 262

    # 测试用例62/129
    print(Solution().numDupDigitsAtMostN(1))  # 0

    # 测试用例63/129
    print(Solution().numDupDigitsAtMostN(9))  # 0

    # 测试用例64/129
    print(Solution().numDupDigitsAtMostN(110))  # 12

    # 测试用例69/129
    print(Solution().numDupDigitsAtMostN(1962))  # 739
